// benchmark_containers.cpp
#include <benchmark/benchmark.h>

#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <list>
#include <memory>
#include <numeric>
#include <random>
#include <vector>

constexpr std::size_t k1K   = 1ULL << 10;  // 1 024
constexpr std::size_t k16K  = 1ULL << 14;  // 16 384
constexpr std::size_t k256K = 1ULL << 18;  // 262 144

// ------------------------------------------------------------
// 填充（写入）基准
// ------------------------------------------------------------

template <std::size_t N>
static void BM_VectorFill(benchmark::State& state) {
    for (auto _ : state) {
        std::vector<int> data;
        data.reserve(N);
        for (std::size_t i = 0; i < N; ++i) {
            data.push_back(static_cast<int>(i));
        }
        benchmark::DoNotOptimize(data.data());
        benchmark::ClobberMemory();
    }
    state.SetItemsProcessed(state.iterations() * static_cast<int64_t>(N));
    state.SetBytesProcessed(state.iterations() *
                            static_cast<int64_t>(N) *
                            static_cast<int64_t>(sizeof(int)));
}

template <std::size_t N>
static void BM_ArrayFill(benchmark::State& state) {
    for (auto _ : state) {
        std::array<int, N> data{};
        for (std::size_t i = 0; i < N; ++i) {
            data[i] = static_cast<int>(i);
        }
        benchmark::DoNotOptimize(data.data());
        benchmark::ClobberMemory();
    }
    state.SetItemsProcessed(state.iterations() * static_cast<int64_t>(N));
    state.SetBytesProcessed(state.iterations() *
                            static_cast<int64_t>(N) *
                            static_cast<int64_t>(sizeof(int)));
}

template <std::size_t N>
static void BM_ListFill(benchmark::State& state) {
    for (auto _ : state) {
        std::list<int> data;
        for (std::size_t i = 0; i < N; ++i) {
            data.push_back(static_cast<int>(i));
        }
        benchmark::DoNotOptimize(data.front());
        benchmark::ClobberMemory();
    }
    state.SetItemsProcessed(state.iterations() * static_cast<int64_t>(N));
    state.SetBytesProcessed(state.iterations() *
                            static_cast<int64_t>(N) *
                            static_cast<int64_t>(sizeof(int)));
}

template <std::size_t N>
static void BM_CArrayFill(benchmark::State& state) {
    for (auto _ : state) {
        auto data = std::make_unique<int[]>(N);
        for (std::size_t i = 0; i < N; ++i) {
            data[i] = static_cast<int>(i);
        }
        benchmark::DoNotOptimize(data.get());
        benchmark::ClobberMemory();
    }
    state.SetItemsProcessed(state.iterations() * static_cast<int64_t>(N));
    state.SetBytesProcessed(state.iterations() *
                            static_cast<int64_t>(N) *
                            static_cast<int64_t>(sizeof(int)));
}

// ------------------------------------------------------------
// 顺序遍历（读）
// ------------------------------------------------------------

template <std::size_t N>
static void BM_VectorSequentialRead(benchmark::State& state) {
    std::vector<int> data(N);
    std::iota(data.begin(), data.end(), 0);
    for (auto _ : state) {
        std::int64_t sum = 0;
        for (int v : data) {
            sum += v;
        }
        benchmark::DoNotOptimize(sum);
    }
    state.SetItemsProcessed(state.iterations() * static_cast<int64_t>(N));
    state.SetBytesProcessed(state.iterations() *
                            static_cast<int64_t>(N) *
                            static_cast<int64_t>(sizeof(int)));
}

template <std::size_t N>
static void BM_ArraySequentialRead(benchmark::State& state) {
    std::array<int, N> data{};
    std::iota(data.begin(), data.end(), 0);
    for (auto _ : state) {
        std::int64_t sum = 0;
        for (int v : data) {
            sum += v;
        }
        benchmark::DoNotOptimize(sum);
    }
    state.SetItemsProcessed(state.iterations() * static_cast<int64_t>(N));
    state.SetBytesProcessed(state.iterations() *
                            static_cast<int64_t>(N) *
                            static_cast<int64_t>(sizeof(int)));
}

template <std::size_t N>
static void BM_ListSequentialRead(benchmark::State& state) {
    std::list<int> data;
    for (std::size_t i = 0; i < N; ++i) {
        data.push_back(static_cast<int>(i));
    }
    for (auto _ : state) {
        std::int64_t sum = 0;
        for (int v : data) {
            sum += v;
        }
        benchmark::DoNotOptimize(sum);
    }
    state.SetItemsProcessed(state.iterations() * static_cast<int64_t>(N));
    state.SetBytesProcessed(state.iterations() *
                            static_cast<int64_t>(N) *
                            static_cast<int64_t>(sizeof(int)));
}

template <std::size_t N>
static void BM_CArraySequentialRead(benchmark::State& state) {
    auto data = std::make_unique<int[]>(N);
    for (std::size_t i = 0; i < N; ++i) {
        data[i] = static_cast<int>(i);
    }
    for (auto _ : state) {
        std::int64_t sum = 0;
        for (std::size_t i = 0; i < N; ++i) {
            sum += data[i];
        }
        benchmark::DoNotOptimize(sum);
    }
    state.SetItemsProcessed(state.iterations() * static_cast<int64_t>(N));
    state.SetBytesProcessed(state.iterations() *
                            static_cast<int64_t>(N) *
                            static_cast<int64_t>(sizeof(int)));
}

// ------------------------------------------------------------
// 随机访问（std::list 不支持高效随机访问，此处不测）
// ------------------------------------------------------------

template <std::size_t N>
static void BM_VectorRandomRead(benchmark::State& state) {
    std::vector<int> data(N);
    std::iota(data.begin(), data.end(), 0);

    std::vector<std::size_t> indices(N);
    std::iota(indices.begin(), indices.end(), 0);
    std::mt19937 rng(1337);
    std::shuffle(indices.begin(), indices.end(), rng);

    for (auto _ : state) {
        std::int64_t sum = 0;
        for (auto idx : indices) {
            sum += data[idx];
        }
        benchmark::DoNotOptimize(sum);
    }
    state.SetItemsProcessed(state.iterations() * static_cast<int64_t>(N));
    state.SetBytesProcessed(state.iterations() *
                            static_cast<int64_t>(N) *
                            static_cast<int64_t>(sizeof(int)));
}

template <std::size_t N>
static void BM_ArrayRandomRead(benchmark::State& state) {
    std::array<int, N> data{};
    std::iota(data.begin(), data.end(), 0);

    std::vector<std::size_t> indices(N);
    std::iota(indices.begin(), indices.end(), 0);
    std::mt19937 rng(1337);
    std::shuffle(indices.begin(), indices.end(), rng);

    for (auto _ : state) {
        std::int64_t sum = 0;
        for (auto idx : indices) {
            sum += data[idx];
        }
        benchmark::DoNotOptimize(sum);
    }
    state.SetItemsProcessed(state.iterations() * static_cast<int64_t>(N));
    state.SetBytesProcessed(state.iterations() *
                            static_cast<int64_t>(N) *
                            static_cast<int64_t>(sizeof(int)));
}

template <std::size_t N>
static void BM_CArrayRandomRead(benchmark::State& state) {
    auto data = std::make_unique<int[]>(N);
    for (std::size_t i = 0; i < N; ++i) {
        data[i] = static_cast<int>(i);
    }

    std::vector<std::size_t> indices(N);
    std::iota(indices.begin(), indices.end(), 0);
    std::mt19937 rng(1337);
    std::shuffle(indices.begin(), indices.end(), rng);

    for (auto _ : state) {
        std::int64_t sum = 0;
        for (auto idx : indices) {
            sum += data[idx];
        }
        benchmark::DoNotOptimize(sum);
    }
    state.SetItemsProcessed(state.iterations() * static_cast<int64_t>(N));
    state.SetBytesProcessed(state.iterations() *
                            static_cast<int64_t>(N) *
                            static_cast<int64_t>(sizeof(int)));
}

// ------------------------------------------------------------
// 注册基准
// ------------------------------------------------------------

#define REGISTER_ALL_SIZES(BENCH)        \
    BENCH(k1K);                          \
    BENCH(k16K);                         \
    BENCH(k256K);

#define REGISTER_VECTOR_FILL(N) BENCHMARK_TEMPLATE(BM_VectorFill, N)->Name("Vector/Fill/" #N);
#define REGISTER_ARRAY_FILL(N)  BENCHMARK_TEMPLATE(BM_ArrayFill,  N)->Name("Array/Fill/"  #N);
#define REGISTER_LIST_FILL(N)   BENCHMARK_TEMPLATE(BM_ListFill,   N)->Name("List/Fill/"   #N);
#define REGISTER_CARRAY_FILL(N) BENCHMARK_TEMPLATE(BM_CArrayFill, N)->Name("CArray/Fill/" #N);

#define REGISTER_VECTOR_SEQ(N) BENCHMARK_TEMPLATE(BM_VectorSequentialRead, N)->Name("Vector/SeqRead/" #N);
#define REGISTER_ARRAY_SEQ(N)  BENCHMARK_TEMPLATE(BM_ArraySequentialRead,  N)->Name("Array/SeqRead/"  #N);
#define REGISTER_LIST_SEQ(N)   BENCHMARK_TEMPLATE(BM_ListSequentialRead,   N)->Name("List/SeqRead/"   #N);
#define REGISTER_CARRAY_SEQ(N) BENCHMARK_TEMPLATE(BM_CArraySequentialRead, N)->Name("CArray/SeqRead/" #N);

#define REGISTER_VECTOR_RAND(N) BENCHMARK_TEMPLATE(BM_VectorRandomRead, N)->Name("Vector/RandRead/" #N);
#define REGISTER_ARRAY_RAND(N)  BENCHMARK_TEMPLATE(BM_ArrayRandomRead,  N)->Name("Array/RandRead/"  #N);
#define REGISTER_CARRAY_RAND(N) BENCHMARK_TEMPLATE(BM_CArrayRandomRead, N)->Name("CArray/RandRead/" #N);

REGISTER_ALL_SIZES(REGISTER_VECTOR_FILL)
REGISTER_ALL_SIZES(REGISTER_ARRAY_FILL)
REGISTER_ALL_SIZES(REGISTER_LIST_FILL)
REGISTER_ALL_SIZES(REGISTER_CARRAY_FILL)

REGISTER_ALL_SIZES(REGISTER_VECTOR_SEQ)
REGISTER_ALL_SIZES(REGISTER_ARRAY_SEQ)
REGISTER_ALL_SIZES(REGISTER_LIST_SEQ)
REGISTER_ALL_SIZES(REGISTER_CARRAY_SEQ)

REGISTER_ALL_SIZES(REGISTER_VECTOR_RAND)
REGISTER_ALL_SIZES(REGISTER_ARRAY_RAND)
REGISTER_ALL_SIZES(REGISTER_CARRAY_RAND)

// Google Benchmark 入口
BENCHMARK_MAIN();